package com.wyl.bloomFilter;

import java.util.BitSet;
import java.util.Random;

/**
 * 目前布隆过滤器已经有相应实现开源类库啦，如 Google  Guava 类库， Twitter  Algebird 类库，信手拈来即可
 */
public class BloomFilter {

    private int bitSetSize; // 位数组大小
    private int hashFunctionCount; // 哈希函数个数
    private BitSet bitSet;
    private Random random = new Random();

    /**
     * @param expectedElementCount 期望布隆过滤器最终存放的元素个数
     * @param falsePositiveRate 误判率
     */
    public BloomFilter(int expectedElementCount, double falsePositiveRate) {
        // 根据期望元素个数和误判率计算位数组大小和哈希函数个数
        this.bitSetSize = (int) Math.ceil(expectedElementCount * (-Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2))));
        this.hashFunctionCount = (int) Math.ceil(Math.log(2) * bitSetSize / expectedElementCount);
        this.bitSet = new BitSet(bitSetSize);
    }

    public void add(String element) {
        for (int i = 0; i < hashFunctionCount; i++) {
            int hashValue = hash(element, i);
            bitSet.set(hashValue, true);
        }
    }

    public boolean contains(String element) {
        for (int i = 0; i < hashFunctionCount; i++) {
            int hashValue = hash(element, i);
            if (!bitSet.get(hashValue)) {
                return false;
            }
        }
        return true;
    }

    private int hash(String str, int seed) {
        random.setSeed(seed);
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash = hash * random.nextInt() + str.charAt(i);
        }
        return Math.abs(hash % bitSetSize);
    }
}
